package medium;

import metastructure.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。
 * （即逐层地，从左到右访问所有节点）。
 *
 *  示例：
 * 二叉树：[3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 *  返回其层序遍历结果：
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 * 
 *  Related Topics 树 广度优先搜索 二叉树
 *  👍 1125 👎 0
 *
 * leetcode submit region begin(Prohibit modification and deletion)
 */
public class L102_二叉树的层序遍历 {

    /**
     * 使用队列，先进先出.
     *
     * 解答成功:
     * 执行耗时:1 ms,击败了89.99% 的Java用户
     * 内存消耗:38.5 MB,击败了64.64% 的Java用户
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        if (root == null) return res;

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();

            List<Integer> list = new ArrayList<>();
            for (int i=0; i<size; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(list);
        }
        return res;
    }
}
